package com.mjx.algorithm.tree;

/**
 * 二叉搜索树
 * Created by meijingxiang on 2017/2/7.
 */
public class SearchTree implements Tree {
    private Node root;
    @Override
    public boolean insert(int data) {
        Node node=new Node();
        node.setData(data);
        if (root == null)
            root = node;
        else {
            Node curNode = root;
            Node curParent;
            while (true){
                curParent = curNode;
                if (data > curNode.getData()){
                    curNode = curNode.getRightChild();
                    if (curNode == null){
                        curParent.setRightChild(node);
                        node.setParent(curParent);
                        break;
                    }
                }
                else {
                    curNode = curNode.getLeftChild();
                    if (curNode == null){
                        curParent.setLeftChild(node);
                        node.setParent(curParent);
                        break;
                    }
                }
            }
        }
        return true;
    }

    @Override
    public Node find(int data) {
        Node curNode = root;
        while (curNode != null){
            if (data == curNode.getData())
                return curNode;
            if (data > curNode.getData()){
                curNode = curNode.getRightChild();
            }
            if (data < curNode.getData()){
                curNode = curNode.getLeftChild();
            }
        }
        return null;
    }

    @Override
    public boolean delete(int data) {
        Node deleteNode = find(data);
        if (deleteNode == null)
            return false;
        Node deleteParent = deleteNode.getParent();
        //删除的是叶子节点
        if (deleteNode.getLeftChild() ==null && deleteNode.getRightChild() ==null){
            if (deleteParent.getLeftChild() == deleteNode)
                deleteParent.setLeftChild(null);
            if (deleteParent.getRightChild() == deleteNode)
                deleteParent.setRightChild(null);
        }
        //删除的节点有两个子节点
        else if (deleteNode.getLeftChild() != null && deleteNode.getRightChild() != null){
            Node houji=deleteNode.getRightChild();
            //一直找到没有左子节点的节点就是后继节点
            while (houji.getLeftChild() != null) {
                houji = houji.getLeftChild();
            }
            //后继节点的父节点的左节点换成后继节点的右节点
            if (houji.getParent() != deleteNode)
                houji.getParent().setLeftChild(houji.getRightChild());
            //被删除的节点的左节点接到后继节点
            houji.setLeftChild(deleteNode.getLeftChild());
            //断掉的左节点父节点设置为后继节点
            if (deleteNode.getLeftChild() != null)
                deleteNode.getLeftChild().setParent(houji);
            if (deleteParent.getLeftChild() == deleteNode)
                deleteParent.setLeftChild(houji);
            if (deleteParent.getRightChild() == deleteNode)
                deleteParent.setRightChild(houji);
        }
        //删除的节点有一个子节点
        else {
            Node childNode = deleteNode.getLeftChild() == null ? deleteNode.getRightChild() : deleteNode.getLeftChild();
            if (deleteParent.getLeftChild() == deleteNode)
                deleteParent.setLeftChild(childNode);
            if (deleteParent.getRightChild() == deleteNode)
                deleteParent.setRightChild(childNode);
        }
        return true;
    }

    public void display(){
        inOrder(root);
        System.out.println();
    }

    private void inOrder(Node curNode){
        if (curNode != null){
            inOrder(curNode.getLeftChild());
            System.out.print(curNode.getData()+" ");
            inOrder(curNode.getRightChild());
        }
    }

    public static void main(String[] args) {
        SearchTree tree = new SearchTree();
        tree.insert(2);
        tree.insert(1);
        tree.insert(3);
        tree.insert(22);
        tree.insert(12);
        tree.insert(15);
        tree.insert(7);
        tree.display();
//        System.out.println(tree.find(12).getData());
        tree.delete(3);
        tree.display();
    }
}
